#include <cstdio>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;

const int Maxn = 100010;
int N, M, A[ Maxn ], Tag[ Maxn << 2 ];
LL Max[ Maxn << 2 ], Min[ Maxn << 2 ], Add[ Maxn << 2 ], Rec[ Maxn << 2 ], Sum[ Maxn << 2 ];

const int MAX_SIZE = 1 << 17;
char *l, *r, buf[ MAX_SIZE ];
inline int gc() {
    if( l == r )
        if( l == ( r = ( l = buf ) + fread( buf, 1, MAX_SIZE, stdin ) ) ) return -1;
    return *l++; 
}
inline void Read( LL &x ) {
    char c = gc();
    for(; c < 48 || c > 57; c = gc() );
    for( x = 0; c > 47 && c < 58; c = gc() )
        x = x * 10 + ( c ^ 48 );
    return;
}
inline void Read( int &x ) {
    char c = gc();
    for(; c < 48 || c > 57; c = gc() );
    for( x = 0; c > 47 && c < 58; c = gc() )
        x = x * 10 + ( c ^ 48 );
    return;
}

void Build( int Index, int Left, int Right );
void Addition( int Index, int Left, int Right, int L, int R, LL X );
void Sqrt( int Index, int Left, int Right, int L, int R );
LL Query( int Index, int Left, int Right, int L, int R );
int main() {
	Read( N ); Read( M );
	for( int i = 1; i <= N; ++i ) Read( A[ i ] );
	Build( 1, 1, N );
	for( int i = 1; i <= M; ++i ) {
		int Opt, l, r;
		Read( Opt ); Read( l ); Read( r );
		if( Opt == 1 ) {
			LL x; 
			Read( x );
			Addition( 1, 1, N, l, r, x );
		}
		if( Opt == 2 ) Sqrt( 1, 1, N, l, r );
		if( Opt == 3 ) printf( "%lld\n", Query( 1, 1, N, l, r ) );
	}
	return 0;
}

inline void Collect( int Index, int Left, int Right ) {
	if( Left == Right ) return;
	Max[ Index ] = max( Max[ Index << 1 ], Max[ Index << 1 | 1 ] );
	Min[ Index ] = min( Min[ Index << 1 ], Min[ Index << 1 | 1 ] );
	Sum[ Index ] = Sum[ Index << 1 ] + Sum[ Index << 1 | 1 ];
	return;
}
inline void TagOn( int Index, int Left, int Right, LL K ) {
	Tag[ Index ] = 1; Rec[ Index ] = K; Add[ Index ] = 0;
	Sum[ Index ] = ( Right - Left + 1 ) * K;
	Max[ Index ] = Min[ Index ] = K;
	return;
}
inline void TagDown( int Index, int Left, int Right ) {
	if( Left == Right ) return;
	int Mid = ( Left + Right ) >> 1;
	if( Tag[ Index ] ) {
		TagOn( Index << 1, Left, Mid, Rec[ Index ] );
		TagOn( Index << 1 | 1, Mid + 1, Right, Rec[ Index ] );
		Tag[ Index ] = 0;
	}
	if( Add[ Index ] ) {
		Add[ Index << 1 ] += Add[ Index ];
		Add[ Index << 1 | 1 ] += Add[ Index ];
		Sum[ Index << 1 ] += ( Mid - Left + 1 ) * Add[ Index ];
		Sum[ Index << 1 | 1 ] += ( Right - Mid ) * Add[ Index ];
		Min[ Index << 1 ] += Add[ Index ];
		Max[ Index << 1 ] += Add[ Index ];
		Min[ Index << 1 | 1 ] += Add[ Index ];
		Max[ Index << 1 | 1 ] += Add[ Index ];
		Add[ Index ] = 0;
	}
	return;
}
void Build( int Index, int Left, int Right ) {
	if( Left == Right ) {
		Max[ Index ] = Min[ Index ] = Sum[ Index ] = A[ Left ];
		return;
	}
	int Mid = ( Left + Right ) >> 1;
	Build( Index << 1, Left, Mid );
	Build( Index << 1 | 1, Mid + 1, Right );
	Collect( Index, Left, Right );
	return;
}
void Addition( int Index, int Left, int Right, int L, int R, LL K ) {
	TagDown( Index, Left, Right );
	if( L <= Left && Right <= R ) {
		Sum[ Index ] += ( Right - Left + 1 ) * K;
		Min[ Index ] += K; Max[ Index ] += K;
		Add[ Index ] += K;
		return;
	}
	int Mid = ( Left + Right ) >> 1;
	if( L <= Mid ) Addition( Index << 1, Left, Mid, L, R, K );
	if( R > Mid ) Addition( Index << 1 | 1, Mid + 1, Right, L, R, K );
	Collect( Index, Left, Right );
	return;
}
void Sqrt( int Index, int Left, int Right, int L, int R ) {
	TagDown( Index, Left, Right );
	if( L <= Left && Right <= R ) { 
		if( ( LL )floor( sqrt( Min[ Index ] ) ) == ( LL )floor( sqrt( Max[ Index ] ) ) ) {
			TagOn( Index, Left, Right, ( LL )floor( sqrt( Min[ Index ] ) ) );
			return;
		}
		if( Min[ Index ] + 1 == Max[ Index ] && 
				( LL )floor( sqrt( Min[ Index ] ) ) + 1 == ( LL )floor( sqrt( Max[ Index ] ) ) ) {
			Addition( Index, Left, Right, L, R, ( LL )floor( sqrt( Min[ Index ] ) ) - Min[ Index ] );
			return;
		}
	}
	int Mid = ( Left + Right ) >> 1;
	if( L <= Mid ) Sqrt( Index << 1, Left, Mid, L, R );
	if( R > Mid ) Sqrt( Index << 1 | 1, Mid + 1, Right, L, R );
	Collect( Index, Left, Right );
	return;
}
LL Query( int Index, int Left, int Right, int L, int R ) {
	TagDown( Index, Left, Right );
	if( L <= Left && Right <= R ) return Sum[ Index ];
	LL Ans = 0;
	int Mid = ( Left + Right ) >> 1;
	if( L <= Mid ) Ans += Query( Index << 1, Left, Mid, L, R );
	if( R > Mid ) Ans += Query( Index << 1 | 1, Mid + 1, Right, L, R );
	return Ans;
}

